import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @作者 钟先崟
 * @时间 2023-03-14 19:53
 * @说明 30. 串联所有单词的子串
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 * s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 * 示例：
 * 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 * 输出：[6,9,12]
 * 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
 * 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
 * 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
 * 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
 */
public class Solution {
    public static void main(String[] args) {
//        findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"}).stream().forEach((Integer a) -> {
//            System.out.print(a + " ");
//        });

        findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "good"}).stream().forEach((Integer a) -> {
            System.out.print(a + " ");
        });
    }

    /**
     * 执行用时：814 ms, 在所有 Java 提交中击败了6.50%的用户
     * 内存消耗：42.2 MB, 在所有 Java 提交中击败了49.70%的用户
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int sLen = s.length();
        int wlen = words[0].length();
        int wsLen = words.length;
        if (sLen < wlen * wsLen) return list;
        List<String> ws = new ArrayList<>();

        for (int i = 0; i < sLen - wlen * wsLen + 1; i++) {
            ws.clear();
            for (int j = 0; j < wsLen; j++) {
                ws.add(words[j]);
            }
            String substring = s.substring(i, i + wlen * wsLen);
            for (int j = 0; j < substring.length(); j = j + wlen) {
                String substring1 = substring.substring(j, j + wlen);
                if (!ws.contains(substring1)) {
                    break;
                } else {
                    ws.remove(substring1);
                }
            }
            if (ws.isEmpty()) {
                list.add(i);
            }
        }
        return list;
    }
}
